package day0509

import "strings"

func replaceWords(dictionary []string, sentence string) string {
	strArray := strings.Fields(sentence)
	trie := New()
	for _, word := range dictionary {
		trie.Insert(word)
	}
	ans := trie.Prefix(strArray[0])
	for i := 1; i < len(strArray); i++ {
		ans += " " + trie.Prefix(strArray[i])
	}
	return ans
}

type Trie struct {
	isEnd    bool
	children [26]*Trie
}

func New() Trie {
	return Trie{}
}

func (t *Trie) Insert(word string) {
	node := t
	for _, c := range word {
		idx := c - 'a'
		if node.children[idx] == nil {
			node.children[idx] = &Trie{}
		}
		node = node.children[idx]
	}
	node.isEnd = true
}

func (t *Trie) Prefix(word string) string {
	ans := ""
	node := t
	for _, c := range word {
		idx := c - 'a'
		if node.isEnd {
			return ans
		}
		if node.children[idx] == nil {
			return word
		}
		node = node.children[idx]
		ans += string('a' + idx)
	}
	return word
}
